package chapter_4.matrix;

import java.util.Arrays;

/**
 * (RecursiveSimple). 
 *
 * @author 汪文波(Wang Wenbo) wenboit@163.com
 * @notes Create on 2021-12-13 07:17
 */
public class RecursiveSimple {

    public static void main(String[] args) {
        int[][] A = new int[][]{{2, 1, 3, 5}, {4, 3, 9, 90}, {13, 56, 102, 11}, {45, 12, 61, 89}};
        int[][] B = new int[][]{{1, 2, 90, 7}, {1, 0, 76, 12}, {190, 20, 56, 8}, {12, 45, 21, 43}};

        int[][] C = multi(A, B);
        System.out.println(Arrays.deepToString(C));

    }

    public static int[][] multi(int[][] A, int[][] B) {
        int rows = A.length;
        int[][] C = new int[rows][rows];

        if (rows == 1) {
            C[0][0] = A[0][0] * B[0][0];
            return C;
        }

        int mid = rows / 2;
        if (mid > 0) {
            int[][] A11, A12, A21, A22;
            int[][] B11, B12, B21, B22;
            int[][] C11, C12, C21, C22;

            int[][][] a = partition(A, mid);
            A11 = a[0];
            A12 = a[1];
            A21 = a[2];
            A22 = a[3];

            int[][][] b = partition(B, mid);
            B11 = b[0];
            B12 = b[1];
            B21 = b[2];
            B22 = b[3];

            C11 = plus(multi(A11, B11), multi(A12, B21));
            C12 = plus(multi(A11, B12), multi(A12, B22));
            C21 = plus(multi(A21, B11), multi(A22, B21));
            C22 = plus(multi(A21, B12), multi(A22, B22));

            C = combine(C11, C12, C21, C22);
        }

        return C;
    }

    private static int[][] combine(int[][] m11, int[][] m12, int[][] m21, int[][] m22) {
        int mid = m11.length;
        int[][] c = new int[mid * 2][mid * 2];
        for (int i = 0; i < mid; i++) {
            for (int j = 0; j < mid; j++) {
                c[i][j] = m11[i][j];
                c[i][j + mid] = m12[i][j];
                c[i + mid][j] = m21[i][j];
                c[i + mid][j + mid] = m22[i][j];
            }
        }

        return c;
    }

    private static int[][][] partition(int[][] matrix, int n) {

        int[][][] arr = new int[4][][];

        for (int i = 0; i < 4; i++) {
            arr[i] = new int[n][n];
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[0][i][j] = matrix[i][j];
                arr[1][i][j] = matrix[i][j + n];
                arr[2][i][j] = matrix[i + n][j];
                arr[3][i][j] = matrix[i + n][j + n];
            }
        }

        return arr;
    }

    private static int[][] plus(int[][] mat_1, int[][] mat_2) {
        int n = mat_1.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = mat_1[i][j] + mat_2[i][j];
            }
        }
        return result;
    }

}
